In cryptography, pseudo random number generators are typically employed to generate some pseudo random numbers for creating a cryptographic key. A well known pseudo random number generator that generates highly randomized numbers, which are strong in a cryptographic sense, is a Blum-Blum-Shub (BBS) pseudo random number generator. The BBS pseudo random number generator uses two large prime numbers, p and q, which are congruent to three, mod four. Their product, n=p*q, is called a Blum integer. An arbitrary integer X larger than both p and q, and relatively prime to n, is chosen. The BBS pseudo random number generator squares X, takes its remainder modulo n. This results in a seed, X0. To generate bits, the BBS pseudo random number generator takes the most recent Xi and squares it, then takes its remainder modulo n. The entire result is Xi+1, and the low order floor(lg(floor(lg(n)))) bits of Xi+1, are the output of one cycle (or iteration) of the BBS pseudo random number generator. The floor function returns the largest integer less than or equal to its argument, and the lg function is the logarithm of its argument in base 2. For example, if n is 21, which is the smallest Blum integer, the BBS pseudo random number generator may generate 2 bits every cycle.
The outputs of the BBS pseudo random number generator are pseudo random bits or pseudo random numbers because they are generated from the same set of initial values, but nevertheless, they approximate the behavior of true random numbers. In other words, the pseudo random numbers are dependent on each other, and thus, exposing too many of a set of pseudo random numbers from a BBS pseudo random number generator may allow someone to crack the code.
The security of the BBS pseudo random number generator rests on the size of n. A larger n generally implies a more secure stream in a cryptographic sense. Note that increasing the number of bits generated at each cycle by 1 may require doubling the size of n. Furthermore, n also influences the period length of the output. One of the properties of n is that every quadratic residue modulo n has four square roots, one of which is also a quadratic residue. A quadratic residue is the residue of a perfect square. For example, 47 is a quadratic residue module 209. Thus, every X in the sequence of pseudo random number is a quadratic residue, and no more than ¼ of the values less than n can be quadratic residues. Thus, there are no more than n/4 distinct states for the BBS pseudo random number generator, so the maximum period is floor(n/4). The bit stream may start repeating itself after n/4 cycles because there are only n/4 distinct states for the BBS pseudo random number generator.